package org.thewares.collection;

object Deque {
      val empty=AlphaDeque.empty;

      def iterateOver[T](dq:Deque[T])=new Iterator[T]{
	    var current=dq;
	    def hasNext = !current.isEmpty;
	    def next={val ret=current.head; current = current.tail; ret; }
      }

}

trait Deque[+A] extends Seq[A] {
      

      def elements: Iterator[A];
      def reverseElements: Iterator[A];


      def isEmpty: Boolean;
      def length:Int;

      def ++[B >: A](s:Seq[B]):Deque[B];

      def :::[B >: A](d:Deque[B]):Deque[B];

      /** Creates a new deque with element added at the end
       *  of the old deque.  This is the same as push and +.
       *
       *  @param  elem        the element to insert
       */
      def enqueue[B >: A](elem: B):Deque[B];

      /** Creates a new deque with element added at the end
       *  of the old deque.  This is the same as push.
       *
       *  @param  elem        the element to insert
       */
      def +[B >: A](elem: B):Deque[B];

      /** Creates a new deque with element added at the end
       *  of the old deque.  This is the same as +.
       *
       *  @param  elem        the element to insert
       */
      def push[B >: A](elem: B):Deque[B];

      /** Returns the element at the end of the Deque.
       */
      def peek:A;


      /** Returns a new Deque with the last element in the deque removed
       *
       *  @throws Predef.NoSuchElementException
       *  @return a new Deque
       */
      def pop:Deque[A];

      /** Returns a tuple with the last element in the deque,
       *  and a new deque with this element removed.
       *
       *  This is the same as (peek,pop);
       *
       *  @throws Predef.NoSuchElementException
       *  @return a tuple with the last element of the deque
       *  and the rest of the Deque
       */
      def peekPop: (A, Deque[A]);


      /** Creates a new deque with element added at the front
       *  of the old deque.  This is the same as ::
       *
       *  @param  elem        the element to insert
       */
      def unshift[B >: A](elem: B):Deque[B];

      /** Creates a new deque with element added at the front
       *  of the old deque. Same as unshift.
       *
       *  @param  elem        the element to insert
       */
      def ::[B >: A](elem: B):Deque[B];
      
      /** Returns a new Deque with the last element in the deque removed
       *
       *  this is the same as tail
       *
       *  @throws Predef.NoSuchElementException
       *  @return a new Deque
       */     
      def shift: Deque[A];

      /** Returns a tuple with the first element and a new Deque with the other elements
       *
       * this is the same as (head,tail)
       *
       *  @throws Predef.NoSuchElementException
       */     
      // This is what s.c.i.Queue does.
      def dequeue: (A, Deque[A]);
      
      /** Returns the first element
       *
       *  @throws Predef.NoSuchElementException
       *  @return the first element 
       */     
      
      def head: A;

      /** Returns a Deque with all the elements except the first
       *
       *  @throws Predef.NoSuchElementException
       *  @return a new Deque
       */     
      def tail: Deque[A];

      // this are for debugging 
      def nodes:Int;
      def depth:Int;
      def state:String;

/* having a reverse with a sensible type is too painful for now */
//      protected def reverseDeque:Deque[A]; // this should go away in 2.8
//      override def reverse:Deque[A]=reverseDeque;  // has to be concrete or fights with Seq.reverse

}
